package org.example.tree;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author liyishan
 * @date 2023/9/25 09:25
 * @apiNote
 */

public class Test00105BuildTree {



    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return dfs(0,preorder.length-1,0,preorder,map);
    }

    public static TreeNode dfs(int preStart, int preEnd, int inorderStart, int[] preorder, Map<Integer,Integer> map){
        if(preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int rootIdx = map.get(rootVal);
        int leftCnt = rootIdx - inorderStart;
        root.left = dfs(preStart+1,preStart+leftCnt,inorderStart,preorder,map);
        root.right = dfs(preStart+leftCnt+1,preEnd,rootIdx+1,preorder,map);
        return root;
    }


    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = 0;
        for(int i = 1 ;i<preorder.length;i++){
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if(node.val != inorder[inorderIndex]){
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            }else{
                while(!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]){
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }


    //4444444444

}
